﻿class Solution
{
public:
	int longestPalindromeSubseq(string s)
	{
		int n = s.size();
		vector<vector<int>> dp(n, vector<int>(n)); // 搞⼀个 dp 表 
		for (int i = n - 1; i >= 0; i--) // 枚举左端点 i 
		{
			dp[i][i] = 1; // 填表的时候初始化 
			for (int j = i + 1; j < n; j++) // 然后从 i + 1 的位置枚举右端点 
			{
				// 分两种情况填写 dp 表 
				if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
				else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
			}
		}
		// 返回结果 
		return dp[0][n - 1];
	}
};